This invention relates to optimal clock timing in an integrated circuit (IC) chip, and particularly to a technique for minimizing clock cycles based on chip design.
Most integrated circuits operate on the principle that the clock arrival time is the same for each flip-flop, so that the minimum clock cycle must be at least equal to the maximum delay for flip-flop pairs. More particularly, the clock cycle is set so that the clock signal arrives at the same time for every flip-flop pair in the chip. However, delays between flip-flop pairs may not be the same for all flip-flop pairs of an IC chip. Thus, some IC chips employ various configurations of flip-flop pairs having different delays, so the delay between members of one flip-flop pair may be different from the delay between member of a different flip-flop pair. Setting the clock cycle to accommodate all flip-flop pairs requires a minimal clock cycle that is at least equal to the maximum delay of the worst-case flip-flop pair. As a result, an unnecessary delay is introduced to the operation of those flip-flop pairs operating with smaller delays.
The present invention is directed to a clock timing schedule to employ the minimum clock cycle.
In its broadest concept, the present invention is directed to finding a minimal clock cycle for any given flip-flop pair of an IC chip, and adding to that cycle such delay as may be necessary for the clock shift for a destination flip-flop.
In one form of the invention, a netlist graph of the cell is provided containing cell pin vertices, auxiliary vertices, and edges between vertices having a length. A clock shift SH(V) is assigned to each auxiliary vertex so that for any two auxiliary vertices, a difference between the clock shift of the two auxiliary vertices is no greater than a design time of the two auxiliary vertices.
In preferred versions of the invention, the clock shift is assigned to each auxiliary vertex such that SH(V1)+DELAY(V1,V2)xe2x88x92SH(V2)xe2x89xa6fxc2x7BOUND(V1,V2), where SH(V1) is the clock shift of a first auxiliary vertex, SH(V2) is the clock shift of a second auxiliary vertex, DELAY(V1,V2) is a maximal delay of the path between the first and second auxiliary vertices, f is a constant, and BOUND(V1,V2) is a timing restriction of the first and second auxiliary vertices. In some forms of the invention, the constant f is calculated by setting f equal to an average or a lower_bound and an upper_bound. The cycle is then found during successive iterations of the process using different values of f until a minimum value of f is found.
The clock shift is assigned to a vertex by finding a cost of the length of the edges of the vertices from an input vertex to an output vertex. A cycle to the edges is found such that a delay may be added to selected edges without affecting clock stability of the graph. More particularly, the auxiliary vertices that define an input or an output to the netlist graph are merged. All auxiliary vertices are then split into input and output auxiliary vertices such that the input vertex has all inputs of the auxiliary vertices and the output vertex has all outputs of the auxiliary verties. An edge having a length of xe2x88x92T is inserted between respective input and output vertices, where T is the length of the clock cycle.
In another form of the invention, the process is carried out by a computer operated by computer code on a computer medium.